package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_102_二叉树的层序遍历 {
    @Test
    public void main() {

        System.out.println(levelOrder(TreeNode.initRoot()).toString());
    }

    /**
    题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

     示例 1：
     输入：root = [3,9,20,null,null,15,7]
     输出：[[3],[9,20],[15,7]]

     示例 2：
     输入：root = [1]
     输出：[[1]]

     示例 3：
     输入：root = []
     输出：[]

    分析：【P 💜💜】
       1.广度优先：使用list存储上层节点   -- 我真垃圾⊙﹏⊙∥
             优化：不用删除节点，而是通过下标记录下一层的开始节点
            --执行用时：1 ms, 在所有 Java 提交中击败了60.89%的用户
            --时长：5分钟
       大神：深度优先遍历
            --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> levelOrder(TreeNode root) {
        //大神：深度优先遍历
        List<List<Integer>> res = new ArrayList<>();
        dfs(root,0,res);
        return  res;

        //1.广度优先：使用list存储上层节点   -
        /*List<List<Integer>> res = new ArrayList<>();
        if(root==null)  return res;
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()){
            int size = list.size();
            List<Integer> rowList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = list.get(0);
                rowList.add(treeNode.val);
                if(treeNode.left!=null)
                    list.add(treeNode.left);
                if(treeNode.right!=null)
                    list.add(treeNode.right);
                list.remove(0);
            }
            res.add(rowList);
        }
        return res;*/
    }

    private void dfs(TreeNode root, int row, List<List<Integer>> res) {
        if(root==null)return;
        if(row==res.size()){
            List<Integer> rowList = new ArrayList<>();
            res.add(rowList);
        }
        res.get(row).add(root.val);
        dfs(root.left,row+1,res);
        dfs(root.right,row+1,res);
    }
}
